//
// Created by isabella on 25-5-30.
//
#include <common.h>
class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = needle.size();
        int n = haystack.size();
        vector<int>next(m,0);
        int k=0;
        for(int i=1;i<m;i++) {
            while(k>0 && needle[k]!=needle[i]) {
                k=next[k-1];
            }
            if(needle[k]==needle[i]) {
                k++;
            }
            next[i]=k;
        }
        int j=0;
        for(int i=0;i<n;i++) {
            while(j>0 && haystack[i]!=needle[j]) {
                j=next[j-1];
            }
            if(haystack[i]==needle[j]) {
                j++;
            }
            if(j==m) {
                return i-m+1;
            }
        }
        return -1;
    }
};